package 变长滑动窗口2

import "math"

// 这个循环 以及取余的思路不太好想
func minSizeSubarray(nums []int, target int) int {
	total := 0
	for _, x := range nums {
		total += x
	}
	ans := math.MaxInt
	left, sum, n := 0, 0, len(nums)
	for right := 0; right < n*2; right++ {
		sum += nums[right%n]
		for sum > target%total {
			sum -= nums[left%n]
			left++
		}
		if sum == target%total {
			ans = min(ans, right-left+1)
		}
	}
	if ans == math.MaxInt {
		return -1
	}
	return ans + target/total*n
}

//package main
//
//import "math"
//
//// minSizeSubarray 寻找无限重复数组nums中，和为target的最短子数组长度
//// 无限数组指：nums可以无限次拼接（如nums = [1,2,3]，无限数组为[1,2,3,1,2,3,1,2,3,...]）
//func minSizeSubarray(nums []int, target int) int {
//    // 1. 计算原数组的总和（用于处理target包含多个完整数组的情况）
//    total := 0
//    for _, x := range nums {
//        total += x
//    }
//
//    // 初始化结果为最大整数（用于后续取最小值）
//    ans := math.MaxInt
//    left := 0       // 滑动窗口左边界
//    currentSum := 0 // 当前窗口的和
//    n := len(nums)  // 原数组长度
//
//    // 2. 核心：用滑动窗口在"双倍长度数组"中寻找符合条件的子数组
//    // 为什么是2n？因为跨原数组边界的子数组（如末尾到开头）最多需要2n长度就能覆盖所有可能
//    for right := 0; right < n*2; right++ {
//        // 计算当前右指针在原数组中的位置（模拟无限数组，通过取模实现）
//        rightIdx := right % n
//        currentSum += nums[rightIdx] // 将当前元素加入窗口和
//
//        // 3. 收缩左边界：当窗口和超过"目标剩余值"时，移除左边界元素
//        // 目标剩余值 = target % total：因为完整数组的总和是total，target可拆分为 k*total + r（r为剩余值）
//        // 我们只需找到和为r的子数组，再加上k个完整数组的长度（k*n）即可
//        for currentSum > target%total {
//            leftIdx := left % n       // 左指针在原数组中的位置
//            currentSum -= nums[leftIdx] // 移除左边界元素
//            left++                    // 左指针右移，缩小窗口
//        }
//
//        // 4. 当窗口和等于目标剩余值时，更新最短子数组长度
//        if currentSum == target%total {
//            // 当前窗口长度 = 右指针 - 左指针 + 1（闭区间长度）
//            currentLen := right - left + 1
//            if currentLen < ans {
//                ans = currentLen
//            }
//        }
//    }
//
//    // 5. 判断是否找到有效子数组
//    if ans == math.MaxInt {
//        // 未找到和为target%total的子数组，说明无法组成target
//        return -1
//    }
//
//    // 6. 最终结果 = 剩余部分的最短子数组长度 + k个完整数组的长度（k = target / total）
//    // k是target中包含的完整数组个数（如target=10, total=3，则k=3，3*3=9，剩余1）
//    return ans + (target / total) * n
//}
